package com.ljy.my_study.leetcode.K个不同整数的子数组;

import java.time.Duration;
import java.time.Instant;

public class TestMain {

//    给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
//
//            （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
//
//    返回 A 中好子数组的数目。
//
//             
//
//    示例 1：
//
//    输入：A = [1,2,1,2,3], K = 2
//    输出：7
//    解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
//    示例 2：
//
//    输入：A = [1,2,1,3,4], K = 3
//    输出：3
//    解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
//             
//
//    提示：
//
//            1 <= A.length <= 20000
//            1 <= A[i] <= A.length
//1 <= K <= A.length
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        int[] A=new int[]{1,2,1,3,4,1,1};
        int K=3;
        Instant start = Instant.now();
        System.out.println(new TestMain().subarraysWithKDistinct(A,K));
        A=new int[]{1,2,1,2,3};
        K=2;
        System.out.println(new TestMain().subarraysWithKDistinct(A,K));
        A=new int[]{1,2,1,3,4};
        K=3;
        System.out.println(new TestMain().subarraysWithKDistinct(A,K));
        Instant end = Instant.now();
        System.out.println(Duration.between(start,end).toMillis());
    }

//    1,2,1,3,4
//
//    1:1;
//    1:1,2:2;
//    1:2,2:1;
//    1:2,2:1,3:1;
//    1:2,2:1,3:1,4:1;

    public int subarraysWithKDistinct(int[] A, int K) {
        int len=A.length;
        int[] count=new int[len+1];
        int result=0;
        int distinctCount=0;
        for(int i=0;i<=len-K;i++){
            result=dfs(A,result,distinctCount,count,i,K);
        }
        return result;
    }

    private int dfs(int[] A,int result,int distinctCount,int[] count,int index,int k){
        int len=A.length;
        if(index>=len){
            return result;
        }
        if(count[A[index]]==0){
            distinctCount++;
            if(distinctCount>k){
                return result;
            }
        }
        if(distinctCount==k){
            result++;
        }
        count[A[index]]++;
        result=dfs(A,result,distinctCount,count,index+1,k);
        count[A[index]]--;
        return result;
    }
}
